package Leetcode.链表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName 合并两个有序链表
 * @since: 2023/8/5 10:41
 * @auth: kirito
 * @description:
 **/
public class 合并两个有序链表 {
//    public static class ListNode {
//        int val;
//        ListNode next;
//        ListNode() {}
//        ListNode(int val) { this.val = val; }
//        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//    }
    //递归
    //把l1 和 l2合并成为一个有序链表
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        else if (list2 == null) {
            return list1;
        } else if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else {
            //把l1 和 l2合并成为一个有序链表
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
    /**
     * 合并两个已排序链表，返回一个新的链表。
     *
     * @param list1 第一个已排序链表的头节点
     * @param list2 第二个已排序链表的头节点
     * @return 合并后的已排序链表的头节点
     */
    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        // 检查链表是否为空
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1; // 返回非空链表，如果有一个为空
        }

        // 创建新链表的头节点
        ListNode head = new ListNode(0);
        ListNode tail = head; // 用于追踪新链表的尾部
        ListNode a = list1, b = list2; // 分别追踪链表 list1 和 list2 的当前节点

        // 遍历链表 list1 和 list2，将较小的节点加入到新链表
        while (a != null && b != null) {
            if (a.val < b.val) {
                tail.next = a; // 将较小节点连接到新链表
                a = a.next; // 移动 list1 的指针到下一个节点
            } else {
                tail.next = b; // 将较小节点连接到新链表
                b = b.next; // 移动 list2 的指针到下一个节点
            }
            tail = tail.next; // 移动新链表的尾指针到刚刚添加的节点
        }

        // 将剩余的链表部分连接到新链表
        tail.next = (a != null ? a : b);

        return head.next; // 返回合并后的链表头节点
    }
    // 交换 h[i] 和 h[j]
    private static void swap(int[] h, int i, int j) {
        int tmp = h[i];
        h[i] = h[j];
        h[j] = tmp;
    }

    /**
     * 一个数组，尽可能的减少交换次序，将数组的前半部分都是正数，后部分都是负数，数组不含0
     * 长度>=2
     * 最后返回交换次数
     * 快排思想
     * @param arr
     * @return
     */
    public static int switch_1(int [] arr) {
        int count = 0;
        int len = arr.length;
        int left = 0, right = len - 1;
        while (left <= right) {
            //越界处理
            if (left < 0 || right > len) {
                break;
            }
            while (arr[left] > 0) {
                left++;
            }
            while (arr[right] < 0) {
                right--;
            }
            //交换后左右指针都移动，count++
            if (arr[left] < 0 && arr[right] > 0 && left < right) {
                swap(arr, left, right);
                left++;
                right--;
                count++;
            }
        }
        return count;
    }


    public static void main(String[] args) {
        int[] arr = {1, -2, 3, -1, 2, -3};
        System.out.println(switch_1(arr));
        System.out.println(Arrays.toString(arr));


//        int[] nums1 = {1, 2, 4};
//        int[] nums2 = {1, 3, 4};
//        ListNode head1 = ListNode.arrayToLinkedList(nums1);
//        ListNode.printLinkedList(head1);
//        ListNode head2 = ListNode.arrayToLinkedList(nums1);
//        ListNode.printLinkedList(head2);
//
//        ListNode listNode = mergeTwoLists(head1, head2);
////        listNode = mergeTwoLists2(head1, head2);
//        ListNode.printLinkedList(listNode);

    }

}


